package com.github.kezhenxu94.playground.java.interview.perfectword;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 即时战略游戏编队 时间限制：C/C++语言 2000MS；其他语言 4000MS 内存限制：C/C++语言 65536KB；其他语言 589824KB
 * 
 * 题目描述： 你正在玩一个RST（即时战略）游戏。此时你已经有很多队士兵，每一队里的士兵战队力相同。
 * 该游戏士兵种类以战斗力区分，既战斗力一样的士兵算作一种。 你想重新调整编队，
 * 
 * 将现有的队列合并成战斗力相同的两队， 请想出有多少种编队方法吧。
 * 
 * 比如：你现在有两队士兵，第一队有4个士兵，每个士兵战斗力都是1，第二队有2个士兵，每个士兵战斗力都是2.
 * 这时你有三种编队方法，可以将这些士兵合并成战斗力相同的两个队伍：
 * 
 * 方法一：队伍1有4个战斗力为1的士兵，队伍2有2个战斗力为2的士兵，两队的战斗力都是4
 * 
 * 方法二：队伍1有2个战斗力为2的士兵，队伍2有4个战斗力为1的士兵，两队的战斗力都是4
 * 
 * 方法三：队伍1有2个战斗力为1的士兵和1个战斗力为2的士兵，队伍2有2个战斗力为1的士兵和1个战斗力为2的士兵，两队的战斗力都是4
 * 
 * @author KeZhenxu
 *
 */
public class PWRST {

	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			String line = sc.nextLine();
			String[] numbers = line.replaceAll("\\{|\\}", "").replaceAll(",", " ").replaceAll("\\s+", " ")
					.split("\\s+");
			int soldierCount = 0;
			for (int i = 0; i < numbers.length / 2; i++)
				soldierCount += Integer.valueOf(numbers[i]);
			int[] skills = new int[soldierCount];
			int index = 0;
			int totalSkill = 0;
			for (int i = 0; i < numbers.length / 2; i++) {
				Arrays.fill(skills, index, index + Integer.valueOf(numbers[i]),
						Integer.valueOf(numbers[i + numbers.length / 2]));
				index += Integer.valueOf(numbers[i]);
				totalSkill += Integer.valueOf(numbers[i]) * Integer.valueOf(numbers[i + numbers.length / 2]);
			}
			int[] result = { 0 };
			backtracking(result, skills, 0, 0, totalSkill / 2, 0);
			System.out.println(result[0] / 2);
		}
	}

	private static void backtracking(int[] result, int[] skills, int skillSoFar, int k, int target, int chooseFrom) {
		for (int i = chooseFrom; i < skills.length; i++) {
			skillSoFar += skills[i];
			if (skillSoFar == target)
				result[0]++;
			else if (skillSoFar < target)
				backtracking(result, skills, skillSoFar, k, target, i + 1);
			else
				break;
		}
	}
}
